A. Field of the Invention
The present invention relates to a culling method and module applied in a 3D graphics system, and more particularly to a culling method and module to speed up culling using a comparison circuit and a culling decision circuit or tables.
B. Description of the Related Art
Generally, there are at least four procedures in the 3D graphics system as shown in FIG. 1. The TnL (Transform and Lighting) Engine 11 receives the 3D-Coordinate Vertex Stream and then transforms it into 2D-Coordinate Vertex Stream. The Culling module 12 receives the 2D-Coordinate Vertex Stream inputs for eliminating the polygons that cannot be seen from a view point. The Setup Engine 13 prepares the 2D-Coordinate Vertex Stream after culling for the Render Engine 14 to load the 3D graphics.
Culling or backface elimination is an operation that compares the orientation of complete polygons with the view point or center of projection and removes those polygons that cannot be seen. If a polygon can not be seen by a viewer from a point of view, then the polygon does not have to be rendered. Thus, the performance of the render engine 14 can be improved by early removing or culling away the invisible portions with respect to a particular viewpoint because the loading of further graphics process has been substantially reduced.
On average, half of the polygons in a polyhedron are back-facing, that is, invisible. To simplify the operational analysis, a triangle is usually used. The test for visibility is straightforward and is carried out in screen space. We calculate the outward normal for a polygon and examine the sign of this vector in z-axis component. If a culling test is performed on a triangle, the sign of the determinant for the triangle must be examined. Thus,   visibility  :=      {                                                                                                            D                     greater than                     0                                    ,                                                                              if                  ⁢                                      xe2x80x83                                    ⁢                                      vertices                    '                                    ⁢                                      xe2x80x83                                    ⁢                  order                  ⁢                                      xe2x80x83                                    ⁢                  is                  ⁢                                      xe2x80x83                                    ⁢                  counterclockwise                                                                                                                          D                     less than                     0                                    ,                                                                                                  if                    ⁢                                          xe2x80x83                                        ⁢                                          vertices                      '                                        ⁢                                          xe2x80x83                                        ⁢                    order                    ⁢                                          xe2x80x83                                        ⁢                    is                    ⁢                                          xe2x80x83                                        ⁢                    clockwise                                    ;                                                              ⁢                      
                    ⁢          D                =                              "LeftBracketingBar"                                                                                x                    1                                                                                        y                    1                                                                                                                    x                    2                                                                                        y                    2                                                                                                                    x                    3                                                                                        y                    3                                                                        "RightBracketingBar"                    =                                                    (                                                      x                    1                                    -                                      x                    2                                                  )                            ⁢                              xe2x80x83                            ⁢                              (                                                      y                    2                                    -                                      y                    3                                                  )                                      -                                          (                                                      x                    2                                    -                                      x                    3                                                  )                            ⁢                              xe2x80x83                            ⁢                              (                                                      y                    1                                    -                                      y                    3                                                  )                                                        ;      
where D is the determinant of the triangle; and Vertices""s coodinates are (x1, y1), (x2, y2) and (x3, y3).
In most cases, the culling test is to calculate the outward normal of a triangle and examine the sign of the determinant for the vertices coordinates of a triangle to differentiate the visible and invisible surface from a viewpoint of a viewer. Thus, when the value of the determinant N is positive and the coordinate orientation is counterclockwise or when the value of the determinant N is negative and coordinate orientation is clockwise, the triangle is visible. Otherwise, the triangle is invisible. Accordingly, the vertices coordinates are (x1,y1),(x2, y2) and (x3,y3). The determinant N after operation is equal to (x1xe2x88x92x3)(y2xe2x88x92y3)xe2x88x92(x2 xe2x88x92x3)(y1xe2x88x92y3) respectively. According to the determinant N, it needs two multiplication operations and five subtraction operations to complete the analysis of one triangle. For a cost-effective design of culling module, it is desirable to provide a culling module without using multipliers.
Accordingly, the object of the present invention is to provide a fast and cost-effective culling method and module, which does not need any multiplication or subtraction operations for finding the vertices coordinates of a triangle. The method of the invention includes the following steps: first, divide the screen space into nine grids according to the positions of the first vertex V1 and the second vertex V2, of a triangle. Continuously, perform a fast culling test for the triangle by examining which grid the third vertex V3 of a triangle is falling on. According to the relative positions of V1, V2 and the grid where the V3 is falling in, a SIGN vector and a corresponding culling decision is obtained by looking up a culling decision table. The culling decision table records all the possible combinations of SIGN vectors, corresponding culling decisions and associated coordinate orientations. Culling a triangle may be quickly determined according to the SIGN vector and the corresponding culling decision of a culling decision table. Furthermore, the advantage of the present invention is that it is simple and easy to be implemented by using only a simple comparison circuit and a culling decision table for the culling test. Since the invention does not use multipliers, so the cost can be further reduced. Moreover, since the culling decision table is small, so the speed of table looking up is obviously faster than the computation speed of the conventional culling test.